package com.wfm.leetcode.editor.cn;
public class PFour16分割等和子集{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean canPartition(int[] nums) {
        // 长度小于2
        if (nums.length < 2) {
            return false;
        }
        // 总和是奇数
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
        if (sum % 2 != 0) {
            return false;
        }

        int m = nums.length;
        int n = sum/2;
        int[][] dp = new int[m][n+1];
        // 初始化第一行
        for (int j = nums[0]; j <= n; j++) {
            dp[0][j] = nums[0];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j <= n; j++) {
                if(j<nums[i]){ // 背包装不下
                    dp[i][j]=dp[i-1][j];
                }else {  // 背包装得下，选择装或者不装的最大
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-nums[i]] + nums[i]);
                }
            }
        }
        return dp[m-1][n]==n;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PFour16分割等和子集().new Solution();
    }
}